package medium.string;

import java.util.Arrays;
import java.util.Comparator;

/**
 * <a href="https://leetcode.cn/problems/maximum-product-of-word-lengths/description/">318. 最大单词长度乘积</a>
 * 给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
 * 示例 1：
 *   输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
 *   输出：16
 *   解释：这两个单词为 "abcw", "xtfn"。
 * 示例 2：
 *   输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
 *   输出：4
 *   解释：这两个单词为 "ab", "cd"。
 * 示例 3：
 *   输入：words = ["a","aa","aaa","aaaa"]
 *   输出：0
 *   解释：不存在这样的两个单词。
 * 提示：
 *   2 <= words.length <= 1000
 *   1 <= words[i].length <= 1000
 *   words[i] 仅包含小写字母
 * @author 刘学松
 * @date 2023-11-06 11:25
 */
public class 最大单词长度乘积 {
    public int maxProduct(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        int length = words.length;
        int[] binary = new int[length], lenArr = new int[length];
        for (int i = 0; i < length; i++) {
            lenArr[i] = words[i].length();
            binary[i] = getBinary(words[i]);
        }
        int max = 0;
        for (int i = length - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if ((binary[i] & binary[j]) == 0) {
                    max = Math.max(max, lenArr[i] * lenArr[j]);
                }
            }
        }
        return max;
    }

    public int getBinary(String word) {
        int binary = 0;
        for (int i = 0; i < word.length(); i++) {
            binary |= 1 << (word.charAt(i) - 'a');
        }
        return binary;
    }
}
